package com.github.yangyishe.p300;

import java.util.HashSet;
import java.util.Set;

/**
 * 202. 快乐数
 * https://leetcode.cn/problems/happy-number/?envType=study-plan-v2&envId=top-interview-150
 *
 * 编写一个算法来判断一个数 n 是不是快乐数。
 *
 * 「快乐数」 定义为：
 *
 * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
 * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
 * 如果这个过程 结果为 1，那么这个数就是快乐数。
 * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 19
 * 输出：true
 * 解释：
 * 12 + 92 = 82
 * 82 + 22 = 68
 * 62 + 82 = 100
 * 12 + 02 + 02 = 1
 * 示例 2：
 *
 * 输入：n = 2
 * 输出：false
 *
 *
 * 提示：
 *
 * 1 <= n <= 231 - 1
 */
public class Problem202 {

    public static void main(String[] args) {
        int n=2;


        Problem202 problem202 = new Problem202();
        boolean happy = problem202.isHappy(n);
        System.out.println(happy);
    }

    /**
     * 思路
     *
     * 已经确定的情况:
     * 1. 是否是快乐数, 与那个位数没有关系. 可以理解为, 一组由0~9组成的数字数组, 能否构建成快乐数组
     * 2. 拆分为数组后, 对数组构建哈希表, 如果n次计算后又遇到相同的哈希值, 则一定不是快乐数; 如果遇到1, 则确定为哈系数
     *
     * 快乐数分析:
     * 假如快乐数都是个数, 则:
     * 0->false
     * 1->true
     * 2
     *  ->4
     *      ->16
     *          ->1+36
     *          ->3*3+7*7=9+49=58
     *          ->5*5+8*8=25*64=89
     *          ->8*8+9*9=64+81=145
     *          ->1*1+4*4+5*5=1+16+25=42
     *          ->4*4+2*2=16+4=20
     *          ->false(形成循环)
     * 3
     *  ->9
     *      ->81
     *      ->8*8+1=65
     *      ->6*6+5*5=36+25=61
     *      ->6*6+1=37
     *      ->3*3+7*7=9+49=58
     *      ->5*5+8*8=25+64=89
     *      ->false(形成循环)
     * 4
     *  ->16
     *      ->1*1+6*6=37
     *      ->3*3+7*7=9+49=58
     *      ->false(形成循环)
     * 5
     *  ->25
     *      ->2*2+5*5=4+25=29
     *      ->2*2+9*9=4+81=85
     *      ->8*8+5*5=64+25=89
     *      ->false(形成循环)
     * 6 (由于是2倍数, 必定循环)
     *  ->36
     *      ->3*3+6*6=9+36=45
     *      -> false
     * 7
     *  ->49
     *      ->4*4+9*9=16+81=97
     *      ->9*9+7*7=81+49=130
     *      ->1+9=10
     *      ->true
     * 8 (由于是2的倍数,必定循环) ->false
     * 9 (3*n)->false
     * 10 -> true
     * 11 -> 2 ->false
     *
     * 19
     *  ->1+81=82
     *      ->64+4=68
     *      ->36+64=100
     *      ->true
     *
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        Set<Integer> integerSet=new HashSet<>();
        int temp=n;
        while(!integerSet.contains(temp)){
            integerSet.add(temp);
            temp=calc(temp);
            if(temp==1){
                return true;
            }
        }

        return false;
    }

    public int calc(int n){
        int temp=0;

        while(n!=0){
            temp+=(n%10)*(n%10);
            n=n/10;
        }

        return temp;
    }

}
